struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    void _kthSmallest(TreeNode* root, int k, int* index, int* ret) {
        if (root == nullptr) {
            return ;
        }

        _kthSmallest(root->left,k,index,ret);
        (*index)++;
        if ((*index) == k)
            *ret = root->val;
        _kthSmallest(root->right,k,index,ret);
    }
    int kthSmallest(TreeNode* root, int k) {
        int index = 0;
        int ret = 0;
        _kthSmallest(root, k, &index, &ret);

        return ret;
    }
};